package club.xiaojiawei.dp;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/5/22 6:40 PM
 * @question 213. 打家劫舍 II
 * @description 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 */
public class Rob213 {

    public static void main(String[] args) {
        Rob213 test = new Rob213();
        int result = test.rob(new int[]{2, 3, 2});
        System.out.println(result);
    }

    /**
     * dp
     * 偷两回
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length < 2){
            return Arrays.stream(nums).sum();
        }
//        从第一个房子开始偷
        int steal = nums[0];
        int notSteal = 0;
        for (int i = 1; i < nums.length; i++) {
            int temp = notSteal;
//            如果不偷当前房子，则前一个房子可偷可不偷（都不会出发警报），所以直接判断是偷了钱多还是不偷钱多
            notSteal = Math.max(steal, notSteal);
//            如果偷当前房子，则前一个房子必不能偷
            steal = nums[i] + temp;
        }
//        notSteal更大，第一个房子偷不偷都无所谓，反正不会触发警报，因为最后一个房子没偷
        if (notSteal > steal){
            return notSteal;
        }
//        从第二个房子开始偷
        int steal2 = nums[1];
        int notSteal2 = 0;
        for (int i = 2; i < nums.length; i++) {
            int temp = notSteal2;
            notSteal2 = Math.max(steal2, notSteal2);
            steal2 = nums[i] + temp;
        }
//        如果两次行窃最后的房子都偷：
//        1.如果两次钱一样，说明第一次没有偷第一个房子
//        2.如果两次钱不一样，说明第一次肯定偷了第一个房子，此时第一次行窃的steal无效
//        3.由于第二次行窃时房子少一个，所以notSteal肯定大于等于notSteal2，所以直接比较notSteal和steal2即可
        return steal == steal2? steal : Math.max(notSteal, steal2);
    }
}
